
#-*- coding: utf-8 -*-
#!/usr/bin/env python
'''
autor: André Guerreiro nº5117
data: 3 de Junho de 2012

arvore kd
'''
from ListasLigadas import *


'''
Classe No
Constroi o nó da árvore
'''
class No:
    '''
    construtor da classe No
    @param key: chave do nó
    @param valor: valor do nó  
    '''
    def __init__(self, key, valor):
        self.key = key
        self.valor = valor

        self.parent = None
        self.left   = None
        self.right  = None        
        pass
    
    '''
    função que converte o nó numa string    
    '''
    def __str__(self):
        s = str(self.key) + ' : ' + str(self.valor)
        s += '('      
        if self.parent == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.parent.key) + ', ' 

        if self.left == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.left.key) + ', ' 

        if self.right == None:
            s += 'None' + ')' 
        else:
            s += str(self.right.key) + ')' 
        return s
    



'''
Classe ArvoreKD
constroi uma árvore de k dimensões
'''    
class ArvoreKD:
    '''
    Construtor da classe ArvoreKD
    '''
    def __init__(self):
        self.root = None

    '''
    Função para inserir nós na árvore
    @param z: nó a inserir
    @return: y: árvore construida
    '''
    def insert(self, z, depth = 0):        
        if not z:
            return None  
        #Guardar os dados na stack
        x = L.malloc(z)
        L.insert(x)
        
        
        k = len(z[0].key)
        axis = depth % k
        
        r =  len(z) -  1
        self.quickSort(z, axis, r)#ordena lista de pontos do nó
       
        med = len(z) //2       
       
        y = z[med] 
           
        y.left = self.insert(z[:med], depth + 1) 
        y.right = self.insert(z[med +1:], depth + 1) 
        
        if y.left != None:
            z[med].left.parent = y
        if y.right != None:
            z[med].right.parent = y
        else:
            y.parent = self.root 

        return y
            
    '''
    Função para remover nó da árvore kd
    @param z: nó a remover
    '''        
    def delete(self, z): 
        x = L.malloc(z)
        
        L.delete(x)#apaga dado da stack 
        L.free(x)  #liberta os espaço de memória onde estava alocado o nó     
        if z.left == None:
            self.transplant(z, z.right)
        elif z.right == None:
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
   
    '''
    Função para pesquisar o valor mínimo da árvore
    @param x: árvore kd a pesquisar mínimo
    @return: x: valor mínimo da árvore
    '''
    def minimum(self, x):
        while x.left != None:
            x = x.left
        return x
     
    
    '''
    Função para reconstruir a árvore 
    quando é removido um nó    
    '''     
    def transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v != None:
            v.parent = u.parent        
     
    '''
    Função quick sort, para ordenar uma lista
    @param A: lista a ordenar
    @param p: pivot
    @param r: valor máximo da lista
    ''' 
    def quickSort(self, A, p, r):
        if (p < r):
            q = self.partition(A, p,r)
            self.quickSort(A, p, q - 1)
            self.quickSort(A, q + 1, r)

    
    '''
    Função complementar ao quick sort
    '''
    def partition(self,A, p, r):
        x = A[r]
        i = p - 1
        for j in range(p, r):
            if(A[j] <= x):
                i = i + 1
                A[i], A[j] = A[j], A[i]
                pass
            pass
        A[i + 1], A[r] = A[r], A[i + 1]
    
        return i + 1           

    
    '''
    Função para passar os valores da árvore kd
    para uma lista
    @param x: árvore kd
    @param  lista: lista que guarda os valores da árvore
    '''
    def inorder_walk(self, x, lista):
        if x != None:
            self.inorder_walk(x.left, lista)
            lista.append( x )
            self.inorder_walk(x.right, lista)
            
    pass




'''
Para testar o funcionamento 
'''  

print "-----------  Arvore KD  -------"
#lista de nós
nos_kd = [None for k in range(9)]

#lista de chaves para os nós
#listaKD = [(1, 1), (0,1), (2,2), (3,2), (1,3), (4, 5), (7,0), (2, 8), (9, 13)]
listaKD = [(1, 1, 3), (0,1,2 ), (2,2,1), (3,2, 5), (1,3,1), (4, 5,0), (7,0,2), (2, 8,9), (9, 1,1)]

#criar nós
nos_kd[0] = No(listaKD[0], "Renoir")
nos_kd[1] = No(listaKD[1], "van Gogh")
nos_kd[2] = No(listaKD[2], "Picasso")
nos_kd[3] = No(listaKD[3], "Manet")
nos_kd[4] = No(listaKD[4], "da Vinci")
nos_kd[5] = No(listaKD[5], "Miguel Angelo")
nos_kd[6] = No(listaKD[6], "Rafael")
nos_kd[7] = No(listaKD[7], "Goya")
nos_kd[8] = No(listaKD[8], "Turner")   

#criar objecto para a árvore
kd = ArvoreKD()

#criar stack
N=len(listaKD)+7
L = LinkedList(N)


listInsert = []
#inserir valores na árvore
tree =  kd.insert(nos_kd)
kd.inorder_walk(tree, listInsert)

'''
Imprimir resultados
'''
for x in listInsert:
    print x
  
    
print "-----------  Nos  -------"
print "MINIMO"
print kd.minimum(tree)    
print "-----------  Apagar  -------"
listDelete = []
kd.delete(nos_kd[1])

kd.inorder_walk(tree, listDelete)

for x in listDelete:
    print x
  
print "-----------  Stack  -------"

L.getMyStack(N)

print "-----------  kd   END  -------"




